rand() random_shuffle() 与srand()结合一起使用以提高结果的随机性。因为默认情况下，rand()的初始种子是确定的，而srand()可以改变初始种子
随机化算法
随机化循环遍历的顺序，将O（n^2）优化为 O(nlogn)
vector<int> ord(n);
for (int i = 0; i < n; i++) ord[i] = i;
random_shuffle(ord.begin(), ord.end());


模拟退火
求解费马点，该点到其他点的距离和最短
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<double,double> PDD;
const int N=110;

int n;
PDD q[N];
double ans=1e8;

double rand(double l,double r)
{
    return (double)rand()/RAND_MAX*(r-l)+l;
}

double get_dist(PDD a,PDD b)
{
    double dx=a.x-b.x;
    double dy=a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}

double calc(PDD p)
{
    double res=0;
    for(int i=0;i<n;i++)
        res+=get_dist(p,q[i]);
    ans=min(ans,res);
    return res;
}

void simulate_anneal()
{
    PDD cur(rand(0,10000),rand(0,10000));
    for(double t=1e4;t>1e-3;t*=0.99)
    {
        PDD np(rand(cur.x-t,cur.x+t),rand(cur.y-t,cur.y+t));
        double dt=calc(np)-calc(cur);
        if(exp(-dt/t)>rand(0,1)) cur=np;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    srand(time(0));

    cin >>n;
    for(int i=0;i<n;i++)
        cin >>q[i].x>>q[i].y;

    for(int i=0;i<100;i++)
        simulate_anneal();

    cout <<round(ans)<<endl;

    return 0;
}

求解一个最优的排列
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int,int> PII;
const int N=55;

int n,m;
PII q[N];
int ans=-1;

int calc()
{
    int res=0;
    for(int i=0;i<m;i++)
    {
        res+=q[i].x+q[i].y;
        if(i<n)
        {
            if(q[i].x==10) res+=q[i+1].x+q[i+1].y;
            else if(q[i].x+q[i].y==10)
                res+=q[i+1].x;
        }
    }
    ans=max(ans,res);
    return res;
}

void simulate_anneal()
{
    for(double t=1e4;t>1e-3;t*=0.99)
    {
        int a=rand()%m,b=rand()%m;
        int x=calc();

        while(a==b||(q[a]==q[b]&&1!=m)) b=rand()%m;
        //特殊情况交换两点位置相同或如果排列的长度为1,小优化

        swap(q[a],q[b]);
        if(n+(q[n-1].x==10)==m)
        {
            int y=calc();
            //此处是完全重复计算，没有利用之前算出来的答案，复杂度会比较高
            //但是有一些可以差量更新，这样会快一点
            int delta=y-x;
            if(exp(delta/t)<(double)rand()/RAND_MAX)
                swap(q[a],q[b]);
        }
        else swap(q[a],q[b]);
    }
}

int main()
{

    srand(time(0));
    cin >>n;
    for(int i=0;i<n;i++)
        cin >>q[i].x>>q[i].y;
    if(q[n-1].x==10) 
    {
        m=n+1;
        cin >>q[n].x>>q[n].y;
    }else
        m=n;
    
    while((double)clock()/CLOCKS_PER_SEC<0.8) simulate_anneal();
    
    cout <<ans<<endl;

    return 0;
}

凯巨的版本（求解最优的排列）：
//排列长度为1的情况需要特殊判断，排列的长度最好在80以内

ll get()
{
    ...
    if(cnt) return 1ll*cnt*1000000001;//如果排列不符合要求则依据偏离程度返回惩罚值，惩罚值是需要大于最大正解
    return ans;//排列满足要求
}
mt19937 mrand(time(0));
const double down = 0.985;
void gao() {
    double teampture=30000;
    double prenow=get();
    vector<int> tmp;
    while(teampture>1e-14) {
        int idx1=mrand()%n+1;
        int idx2=mrand()%n+1;

        while(idx2==idx1||(tmp[idx1]==tmp[idx2]&&k!=m)) idx2=mrand()%tmp.size();
        //特殊情况交换两点位置相同或如果排列的长度为1

        swap(a[idx1],a[idx2]);
        double pre=prenow;
        double now=get();//越小越好
        double e=exp(fabs(pre-now)/teampture);
        if(now<=pre||1.0/(1+e)>mrand()%100000*1.0/100000) {
            prenow=now;
        }else swap(a[idx1],a[idx2]);
        teampture*=down;
    }
}
int t=60;
while(t--) {
    for(int i=1;i<=n;i++) a[i]=b[i];
    random_shuffle(a+1,a+1+n);
    gao();
}


爬山法
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 15;

int n;
double d[N][N];
double ans[N], dist[N], delta[N];

void calc()
{
    double avg = 0;
    for (int i = 0; i < n + 1; i ++ )
    {
        dist[i] = delta[i] = 0;
        for (int j = 0; j < n; j ++ )
            dist[i] += (d[i][j] - ans[j]) * (d[i][j] - ans[j]);
        dist[i] = sqrt(dist[i]);
        avg += dist[i] / (n + 1);
    }
    for (int i = 0; i < n + 1; i ++ )
        for (int j = 0; j < n; j ++ )
            delta[j] += (dist[i] - avg) * (d[i][j] - ans[j]) / avg;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n + 1; i ++ )
        for (int j = 0; j < n; j ++ )
        {
            scanf("%lf", &d[i][j]);
            ans[j] += d[i][j] / (n + 1);
        }

    for (double t = 1e4; t > 1e-6; t *= 0.99995)
    {
        calc();
        for (int i = 0; i < n; i ++ )
            ans[i] += delta[i] * t;
    }
    for (int i = 0; i < n; i ++ ) printf("%.3lf ", ans[i]);

    return 0;
}
